package containers

import (
	"fmt"
	"math/rand"
	"strconv"
	"strings"
	"time"
)

func MergeSort(arr *[]int) {
	mergeSort(arr, 0, len(*arr)-1)
}
func mergeSort(arr *[]int, l, r int) {
	if l >= r {
		return
	}
	m := l + (r-l)/2
	mergeSort(arr, l, m)
	mergeSort(arr, m+1, r)
	if (*arr)[m] > (*arr)[m+1] {
		mergeTwoArr(arr, l, m, r)
	}
}
func mergeTwoArr(arr *[]int, l, m, r int) {
	tempArr := make([]int, r-l+1)
	if copy(tempArr, (*arr)[l:r+1]) == 0 {
		fmt.Println("copy arr failured!!!")
	}
	a1 := 0
	a2 := m + 1 - l
	for i := l; i <= r; i++ {
		if a1 > m-l {
			(*arr)[i] = tempArr[a2]
			a2++
			continue
		}
		if a2 > r-l {
			(*arr)[i] = tempArr[a1]
			a1++
			continue
		}
		if tempArr[a1] < tempArr[a2] {
			(*arr)[i] = tempArr[a1]
			a1++
		} else {
			(*arr)[i] = tempArr[a2]
			a2++
		}
	}
}

func MergeSort2(arr *[]int) {
	tmpArr := make([]int, len(*arr))
	mergeSort2(arr, 0, len(*arr)-1, &tmpArr)
}
func mergeSort2(arr *[]int, l, r int, tmpArr *[]int) {
	if l >= r {
		return
	}
	m := l + (r-l)/2
	mergeSort2(arr, l, m, tmpArr)
	mergeSort2(arr, m+1, r, tmpArr)
	if (*arr)[m] > (*arr)[m+1] {
		mergeTwoArr2(arr, l, m, r, tmpArr)
	}
}
func MergeSort4(arr *[]int) {
	tmpArr := make([]int, len(*arr))
	mergeSort4(arr, 0, len(*arr)-1, &tmpArr)
}
func mergeSort4(arr *[]int, l, r int, tmpArr *[]int) {
	if r-l < 50 {
		InsertSort3(arr, l, r)
		return
	}
	m := l + (r-l)/2
	mergeSort4(arr, l, m, tmpArr)
	mergeSort4(arr, m+1, r, tmpArr)
	if (*arr)[m] > (*arr)[m+1] {
		mergeTwoArr2(arr, l, m, r, tmpArr)
	}
}
func mergeTwoArr2(arr *[]int, l, m, r int, tmpArr *[]int) {
	if copy((*tmpArr)[l:r+1], (*arr)[l:r+1]) == 0 {
		fmt.Println("copy arr failured!!!")
	}
	a1 := l
	a2 := m + 1
	for i := l; i <= r; i++ {
		if a1 > m {
			(*arr)[i] = (*tmpArr)[a2]
			a2++
			continue
		}
		if a2 > r {
			(*arr)[i] = (*tmpArr)[a1]
			a1++
			continue
		}
		if (*tmpArr)[a1] < (*tmpArr)[a2] {
			(*arr)[i] = (*tmpArr)[a1]
			a1++
		} else {
			(*arr)[i] = (*tmpArr)[a2]
			a2++
		}
	}
}

func MergeSort3(arr *[]int) {
	tmpArr := make([]int, len(*arr))
	mergeSort3(arr, &tmpArr)
}
func mergeSort3(arr *[]int, tmpArr *[]int) {
	for i := 1; i < len(*arr); i += i {

		for j := 0; j+i < len(*arr); j += i + i {
			if (*arr)[j+i] < (*arr)[j+i-1] {
				if j+i+i-1 > len(*arr)-1 {
					mergeTwoArr2(arr, j, j+i-1, len(*arr)-1, tmpArr)
				} else {
					mergeTwoArr2(arr, j, j+i-1, j+i+i-1, tmpArr)
				}
			}
		}
	}
}

func BubbleSort(arr *[]int) {
	aLen := len(*arr)
	for end := aLen - 1; end > 0; end-- {
		for start := 0; start < end; start++ {
			if (*arr)[start] > (*arr)[start+1] {
				(*arr)[start+1], (*arr)[start] = (*arr)[start], (*arr)[start+1]
			}
		}
	}
}
func TimeSort(sortName string, arr *[]int) {
	var now time.Time
	if sortName == "BubbleSort" {
		now = time.Now()
		BubbleSort(arr)
	} else if sortName == "MergeSort" {
		now = time.Now()
		MergeSort(arr)
	} else if sortName == "MergeSort2" {
		now = time.Now()
		MergeSort2(arr)
	} else if sortName == "MergeSort3" {
		now = time.Now()
		MergeSort3(arr)
	} else if sortName == "SelectSort" {
		now = time.Now()
		SelectSort(arr)
	} else if sortName == "InsertSort" {
		now = time.Now()
		InsertSort(arr)
	} else if sortName == "InsertSort2" {
		now = time.Now()
		InsertSort2(arr)
	} else if sortName == "MergeSort4" {
		now = time.Now()
		MergeSort4(arr)
	}
	fmt.Printf("%s spend time: %s\n", sortName, time.Since(now).String())
}
func CreateRandomIntArr(arrLen, arrScale int) *[]int {
	a := make([]int, 0, arrLen)
	for i := 0; i < arrLen; i++ {
		a = append(a, rand.Intn(arrScale)+1)
	}
	return &a
}
func TraverseArr(arr *[]int) {
	sb := strings.Builder{}
	for _, v := range *arr {
		//fmt.Printf("%d ", v)
		sb.WriteString(strconv.Itoa(v) + " ")
	}
	//fmt.Println()
	fmt.Println(sb.String())
}
func VerifyArrIsSorted(arr *[]int) bool {
	aLen := len(*arr)
	for i := 1; i < aLen; i++ {
		if (*arr)[i] < (*arr)[i-1] {
			return false
		}
	}
	return true
}
